//
// Created by zhouyi on 2020/7/1.
//

#include "LeetCode0718.h"
#include "LeetCodeUtils.h"

int main(int argc, char *argv[]) {
    auto *solution = new Solution();
    vector <int> vectorA{ 1, 2, 3, 2, 1 }, vectorB{ 3, 2, 1, 4, 7 };
    int s = solution->findLength(vectorA, vectorB);
    cout << s << "结果";
    return 0;
}

///////////////////////////////////////////////////////////////////////////
// 方法：滑动窗口
///////////////////////////////////////////////////////////////////////////

int Solution::maxLength(vector <int> &a, vector <int> &b, int addA, int addB, int length) {
    int finishResult = 0, curResult = 0;
    for (int i = 0; i < length; i++) {
        if (a[addA + i] == b[addB + i]) {
            curResult++;
        } else
            curResult = 0;
        finishResult = max(finishResult, curResult);
    }

    return finishResult;
}

int Solution::findLength(vector <int> &A, vector <int> &B) {
    printVector(A);

    int aSize = A.size();
    int bSize = B.size();
    int finishResult = 0;

    for (int i = 0; i < bSize; ++i) {
        int length = min(bSize, aSize - i);
        int maxLen = maxLength(A, B, i, 0, length);
        finishResult = max(finishResult, maxLen);


    }

    for (int i = 0; i < aSize; i++) {
        int len = min(aSize, bSize - i);
        int maxLen = maxLength(A, B, 0, i, len);
        finishResult = max(finishResult, maxLen);
    }
    return finishResult;
}

///////////////////////////////////////////////////////////////////////////
// 动态规划
///////////////////////////////////////////////////////////////////////////



